/*
写出一个算法确定一个有n个顶点e条边的无向图是否包含回路，
所设计的算法的时间复杂度应该是O(n + e)。
*/

#include "ADJ_List.h"
#include "iostream"
#include <queue>
using namespace std;

/*****核心功能函数*****/
bool HasCirclePath(Graph_ADJ_List &g, int v)
{
    using std::queue;
    queue<int> q;
    g.mark[v] = true;
    q.push(v);
    while (!q.empty())
    {
        int v = q.front();
        q.pop();
        for (Edge e = g.firstE(v); g.isE(e); e = g.nextE(e))
        {
            if (!g.mark[e.to])
            {
                g.mark[e.to] = true;
                q.push(e.to);
            }
            else
            {
                return true;
            }
        }
    }

    /*
    for (int i = 0; i < v; i = i + 1) //图可以被分成不止一部分
    {
        if (!g.mark[i])
        {
            if (HasCirclePath(g, i))
            {
                return true;
            }
        }
    }
    */

    return false;
}
/*****核心功能函数*****/

/*****主函数*****/
int main()
{

    Graph_ADJ_List *g1 = new Graph_ADJ_List(1);
    cout << "g1中";
    if (HasCirclePath(*g1, 0))
    {
        cout << "存在回路！\n\n";
    }
    else
    {
        cout << "不存在回路！\n\n";
    }

    Graph_ADJ_List *g2 = new Graph_ADJ_List(5);
    g2->setE(0, 1, 0);
    g2->setE(1, 2, 0);
    g2->setE(1, 3, 0);
    g2->setE(2, 4, 0);
    g2->setE(3, 4, 0);
    cout << "g2中";
    if (HasCirclePath(*g2, 0))
    {
        cout << "存在回路！\n\n";
    }
    else
    {
        cout << "不存在回路！\n\n";
    }

    Graph_ADJ_List *g3 = new Graph_ADJ_List(5);
    cout << "g3中";
    if (HasCirclePath(*g3, 0))
    {
        cout << "存在回路！\n\n";
    }
    else
    {
        cout << "不存在回路！\n\n";
    }

    Graph_ADJ_List *g4 = new Graph_ADJ_List(5);
    g4->setE(0, 1, 0);
    g4->setE(1, 2, 0);
    g4->setE(2, 3, 0);
    g4->setE(3, 4, 0);
    /*
    g4->setE(4, 3, 0);
    g4->setE(3, 2, 0);
    g4->setE(2, 1, 0);
    g4->setE(1, 0, 0);
    */
    cout << "g4中";
    if (HasCirclePath(*g4, 0))
    {
        cout << "存在回路！\n\n";
    }
    else
    {
        cout << "不存在回路！\n\n";
    }

    Graph_ADJ_List *g5 = new Graph_ADJ_List(5);
    g5->setE(0, 0, 0);
    g5->setE(1, 2, 0);
    g5->setE(1, 3, 0);
    g5->setE(2, 4, 0);
    g5->setE(3, 4, 0);
    cout << "g5中";
    if (HasCirclePath(*g5, 0))
    {
        cout << "存在回路！\n\n";
    }
    else
    {
        cout << "不存在回路！\n\n";
    }

    Graph_ADJ_List *g6 = new Graph_ADJ_List(5);
    g6->setE(0, 1, 0);
    g6->setE(1, 2, 0);
    g6->setE(2, 3, 0);
    g6->setE(3, 2, 0);
    g6->setE(2, 4, 0);
    cout << "g6中";
    if (HasCirclePath(*g6, 0))
    {
        cout << "存在回路！\n\n";
    }
    else
    {
        cout << "不存在回路！\n\n";
    }

    /*
    Graph_ADJ_List *g7 = new Graph_ADJ_List(5);
    g7->setE(1, 2, 0);
    g7->setE(1, 3, 0);
    g7->setE(2, 4, 0);
    g7->setE(3, 4, 0);
    cout << "g7中";
    if (HasCirclePath(*g7, 0))
    {
        cout << "存在回路！\n\n";
    }
    else
    {
        cout << "不存在回路！\n\n";
    }
    */

    /*
    Graph_ADJ_List *g7 = new Graph_ADJ_List(5);
    g7->setE(0, 1, 0);
    g7->setE(1, 2, 0);
    g7->setE(1, 3, 0);
    g7->setE(2, 4, 0);
    g7->setE(3, 4, 0);
    cout << "g7中";
    if (HasCirclePath(*g7, 3)) //从顶点3开始
    {
        cout << "存在回路！\n\n";
    }
    else
    {
        cout << "不存在回路！\n\n";
    }
    */

    system("pause");
}
/*****主函数*****/